Skip to main content

비선점 스케줄링


비선점 스케줄링이란?​



프로세스가 자원을 할당받았을 경우 자원을 스스로 반납할 때 까지 계속 그 자원을 사용하도록 허용하는 정책이다.

작업 실행 시간 전체 또는 한 번의 CPU배당에 대해 적용되며, 비선점 스케줄링의 예로는 우선순위, FCFS, SJF, HRN 스케줄링 등이 있다.


FCFS 스케줄링 (First Come First Served Scheduling)​


  • 프로세스의 도착순으로 CPU를 배정 (실행 중 입출력을 요구하면 다시 다음 준비 상태에서 FCFS 적용)
  • Batch 작업등, 장기 스케줄러에서 사용 가능
  • 수행 중인 긴 작업을 여러 개의 짧은 작업들이 기다리게 되는 호위효과 (Convoy Effect)의 문제가 발생 할 수 있음

작업Burst Time
P124
P23
P33

위와 같은 작업의 도착 순서는 P1 -> P2 -> P3 이고, 간트차트로 나타내면 다음과 같다.


FCFS


  • 평균 반환시간 = (24+27+30) / 3 = 27
  • 평균 대기시간 = (0+24+27) / 3 = 17

최단 작업 우선 스케줄링 (SJF, Shortest Job First Scheduling)​


  • 대기하는 작업 중 CPU Burst Time이 가장 작은 작업에 CPU를 할당하는 기법
  • 평균 대기 시간에 있어 최적의 알고리즘
  • CPU 요구시간(Burst TIme)을 미리 알기가 어렵다.

작업Burst TIme
P16
P23
P38
P47

위와 같은 작업이 있다면 순서는 Burst Time이 작은 P2 -> P1 -> P4 -> P3 이다. 간트차트로 나타낸다면 다음과 같다.


SJF


  • 평균 반환시간 = (3+9+16+24) / 4 = 13
  • 평균 대기시간 = (3+0+16+9) / 4 = 7

HRN 스케줄링​


  • 실행시간이 긴 프로세스에 불리한 것으로, 대기 시간과 서비스 시간을 이용하는 기법
  • SJF의 약점을 본완한 기법으로 긴 작업과 짧은 작업 간 불평등 완화
  • 우선순위 계산 공식 = (대기시간 + 서비스시간) / 서비스시간
  • 우선순위 계산 결과값이 높은 것 부터 우선 순위가 부여, 대기 시간이 긴 프로세스일 경우 계산 결과값이 높게 나옴

작업대기시간서비스시간
P155
P2106
P3157
P4208

위와 같은 작업일 경우,

  • P1 우선순위 = (5+5)/5 = 2
  • P2 우선순위 = (10+6)/6 = 2.66..
  • P3 우선순위 = (15+7)/7 = 3.14..
  • P4 우선순위 = (20+8)/8 = 3.5

이므로

작업 순서는 P4 -> P3 -> P2 -> P1 이다.


우선순위 스케줄링 (Priority Scheduling)​


  • 각 프로세스의 우선순위가 정해지면, 우선순위가 제일 높은 프로세스에게 CPU를 할당하되, 우선순위가 같은 경우 FCFS 방식을 적용한다.

  • 일반적인 연산 위주 프로세스보다 입출력 위주 프로세스에게 높은 우선순위를 부여하여 대화성을 증진시킨다.

  • 우선순위가 높은 작업이 계속적으로 들어올 경우 우선순위가 낮은 작업은 준비상태에서 보장 없이 머물게 된다 (기아상태). 이런 문제는 시스템에 머무는 시간이 증가할수록 우선순위를 높여주는 에이징으로 해결한다.

  • 우선순위 스케줄링 알고리즘은 일반적으로 가장 많이 쓰이는 스케줄링 기법이다.

  • 내부적 우선순위 고려 : 제한 시간, 메모리 요구량, 사용하는 파일 수, 평균 CPU Burst에 대한 평균 I/O Burst의 비율 등

  • 외부적 우선순위 고려 : 사용료, 정책적인 변수 등


작업Burst Time우선순위
P1103
P211
P323
P414
P552

위와 같은 작업이 있다면 순서는 우선 순위 순대로 가되, 우선순위가 같은 P1,P3의 경우 먼저 도착한 순인 P1 -> P3 순이다.


작업순서 : P2 -> P5 -> P1 -> P3 -> P4


priority


  • 평균 반환시간 = (16+1+18+19+6) / 5 = 12
  • 평균 대기시간 = (6+0+16+18+1) / 5 = 8.2

면접에 나올 수 있는 질문​


Q. 비선점 스케줄링이란?

A. 프로세스가 자원을 할당받았을 경우 자원을 스스로 반납할 때 까지 계속 그 자원을 사용하도록 허용하는 정책


Q. 비선점 스케줄링 알고리즘의 특징과 차이점

A. 각 방식의 특징과 차이점에 대해 서술


참고​



기여자​



Jongminfire
📦